package com.tys.algorithm.advanced.code.class46;

// 本题测试链接 : https://leetcode.com/problems/remove-boxes/
public class Code02_RemoveBoxes {

    //方法1：
    // arr[L...R]消除，而且前面跟着K个arr[L]这个数
    // 返回：所有东西都消掉，最大得分
    public static int func1(int[] arr, int L, int R, int K) {
        //不是有效范围返回0
        if (L > R) {
            return 0;
        }
        //(L+1...R位置跟着0个) + (K个跟着L一起消除：K+1)
        int ans = func1(arr, L + 1, R, 0) + (K + 1) * (K + 1);

        // 前面的K个X，和arr[L]数，合在一起了，现在有K+1个arr[L]位置的数
        for (int i = L + 1; i <= R; i++) {
            //找相同L位置
            if (arr[i] == arr[L]) {
                // 先消除L+1到i-1的数：跟着0个数的最大分数 + 消除i到R的数：跟着K+1个最大分数
                ans = Math.max(ans, func1(arr, L + 1, i - 1, 0) + func1(arr, i, R, K + 1));
            }
        }
        return ans;
    }

    //方法2：
    public static int removeBoxes1(int[] boxes) {
        int N = boxes.length;
        int[][][] dp = new int[N][N][N];
        int ans = process1(boxes, 0, N - 1, 0, dp);
        return ans;
    }

    public static int process1(int[] boxes, int L, int R, int K, int[][][] dp) {
        if (L > R) {
            return 0;
        }
        if (dp[L][R][K] > 0) {
            return dp[L][R][K];
        }
        int ans = process1(boxes, L + 1, R, 0, dp) + (K + 1) * (K + 1);
        for (int i = L + 1; i <= R; i++) {
            if (boxes[i] == boxes[L]) {
                ans = Math.max(ans, process1(boxes, L + 1, i - 1, 0, dp) + process1(boxes, i, R, K + 1, dp));
            }
        }
        dp[L][R][K] = ans;
        return ans;
    }

    //方法3：
    public static int removeBoxes2(int[] boxes) {
        int N = boxes.length;
        int[][][] dp = new int[N][N][N];
        int ans = process2(boxes, 0, N - 1, 0, dp);
        return ans;
    }

    public static int process2(int[] boxes, int L, int R, int K, int[][][] dp) {
        if (L > R) {
            return 0;
        }
        if (dp[L][R][K] > 0) {
            return dp[L][R][K];
        }
        // 找到开头，最后一个1
        // 1,1,1,1,1,5
        // 3 4 5 6 7 8
        //         !
        int last = L;
        //last最后的1位置
        //last+1还有位置 && last+1等于L位置数
        while (last + 1 <= R && boxes[last + 1] == boxes[L]) {
            last++;
        }
        // 计算总的1个数：last之前几个1
        // K个1 (K + last - L) last
        int pre = K + last - L;
        //last位置是1，pre个1和last一起消除 + 后边接着消
        int ans = (pre + 1) * (pre + 1) + process2(boxes, last + 1, R, 0, dp);
        //last+1肯定不是1，因为不是才会停到last
        for (int i = last + 2; i <= R; i++) {
            //找到第一个1
            //i位置 == L位置 && i-1位置！=L位置
            if (boxes[i] == boxes[L] && boxes[i - 1] != boxes[L]) {
                //消中间 + 和并1
                ans = Math.max(ans, process2(boxes, last + 1, i - 1, 0, dp) + process2(boxes, i, R, pre + 1, dp));
            }
        }
        dp[L][R][K] = ans;
        return ans;
    }

}
